package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 二叉树的最近公共祖先
 * @date 2025/4/26 15:29
 */
public class LowestCommonAncestor_236 {

    /**
     * dmsxl解法：dfs-递归-后序
     * <p>
     * 为什么后序？
     * 1.若要判断node是否为p、q的公共祖先节点，相当于，递归判断node的左或右子树是否为p、q的公共祖先节点。
     * 2.要判断当前节点的孩子节点是否为p、q，那只能用后序遍历，才能先访问孩子节点的信息。
     *
     * <p>
     * 两种情况：
     * 1.第三个节点为p、q的公共祖先节点；
     * 按下面遍历方式即可。
     * 2.p、q中任一个，为公共祖先节点；
     * 假设p，当后序遍历到节点p时，root==p，就直接向上返回了，不会在当前分支继续向下递归。
     * 那为什么不往下递归，也没判断q，如何知道节点q在以p为根的树里面？
     * ——因为，首先，题目要求p、q一定存在，且每个节点值不等；其次，如果q不在p下面，那q一定在和p不同的分支中，这就变成了情况1。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p) return p;
        if (root == q) return q;

        // 左
        TreeNode left = lowestCommonAncestor(root.left, p, q);

        // 右
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 中
        // 左子树出现p或者q，右子树也出现p或q，又因为题目要求节点值不相同，所以root是p、q的公共祖先
        if (left != null && right != null) return root;
        // 左子树出现过p或q，右子树没有，所以先返回left；
        // 此时有两种情况：1）p、q的公共祖先节点不是它俩本身，那么后面一定出现right!=null；2）p、q其中有一个是公共祖先节点，那么左子树left中记录的就是该节点，所以直接返回left。
        if (left != null && right == null) return left;
        // 解释同上
        if (left == null && right != null) return right;

        //  左右子树都没出现过p、q
        return null;
    }

}
